T1 大数

Description

给定一个长度为 $n$ 的十进制数 s 和一个质数 $p$ 。 $q$ 次询问，每次给定 $l\ r$ ，询问有多少十进制数 s[x:y] $(l\leq x\leq y\leq r)$ 能被 $p$ 整除。
$1\leq n,q\leq 2\times 10^5,p\leq 2\times 10^9$

Description

给定一个 $n$ 列的表格，每列的高度 $h_i$ 各不相同，但底部对齐，然后向表格中填入 $k$ 个相同的数，填写时要求不能有两个数在同一列。若两个数在同一行，但是中间某一列断开是被允许的，否则也不允许。求填数的方案数对 $10^9+7$ 取模的值。
$n\leq 500,h_i\leq 10^6$

Solution

T1 菜肴制作

Description

有 $n$ 道菜和有 $m$ 条要求，每条要求形如“A 号菜需要在 B 号菜的前面”。现在要求给出一个上菜序列，在满足所有要求的前提下，满足：

阅读全文 »

Description

给定一个串，把串分成偶数段，假设为 $s_1,s_2,\cdots,s_k$ ，要求满足 $s_1=s_k,s_2=s_{k-1},\cdots$ ，求方案数。
$n\leq 10^5$

Solution

source：区间本质不同子串(Luogu6292) 区间本质不同回文子串(bzoj5384)

两个问题都可以归结为「区间本质不同元素个数」。解决这个问题有两个十分常用的方法：

阅读全文 »

换根 dp 是一个广为流传的算法。
换根 dp 对于 dp 方程是有要求的，一般而言 dp 方程中只能含有常数和与 i 的子树有关的项。
本文将探讨对于下述方程如何使其可以换根处理

$f[p]=(\sum_{e} w_e\times f[son])+\text{dep}_p$

Description

有 $n$ 个点，初始时互不连通。有 $q$ 次操作，分别为如下三种类型：

• 连接 $x\ y$ 两个点。保证 $x\ y$ 不连通。
阅读全文 »

T1 word

Description

你有一个由小写字母组成的长度为 $n$ 的字符串。每一步你要找到它的子串中最短的重复块（一个重复块由一个字符串与自身连接而成）。如果有多于一个，你必须选择最左边的那个。你要将那个形如 XX(X - 某个字符串)的重复块替换成 X，即删除其中的一个 X。重复以上步骤直到字符串中不存在重复块。
输出最终的字符串。

Description

给定长度为 $n$ 的字符串 s ，要求构造字符串序列 $s_1,s_2,\cdots,s_k$ ，满足 $\forall i\in[1,k]$ ，$s_i$ 是 s 的子串，且 $\forall i\in[2,k]$， 都有 $s_{i-1}$ 在 $s_i$ 中至少出现了两次（可以有重叠部分）。$s_i$ 不能为空。求最大的 $k$ 值。
$1\leq n\leq 2\times 10^5$

Solution

Description

给定一棵以 $1$ 为根的有 $3n+1$ 个节点的树，树上每个节点均有一个输出端。树上有 $n$ 个节点有 $3$ 个子节点，其余的 $2n+1$ 个节点无子节点（也就是叶子）。$2n+1$ 个节点的初始值均为 $0/1$ ，并且已经提前知道；剩余 $n$ 个节点的值为其 $3$ 个子节点中出现次数最多的值。$q$ 次询问，每次改变一个叶子节点的值，求操作后根节点的值。
$n,q\leq 5\times 10^5$

Solution